package offer2

/**
原题链接:
https://leetcode.cn/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/?envType=study-plan&id=lcof&plan=lcof&plan_progress=bwt37je

剑指 Offer 32 - III. 从上到下打印二叉树 III
请实现一个函数按照之字形顺序打印二叉树，
即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。


例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9  20
/  \
15   7

返回其层次遍历结果：
[
[3],
[20,9],
[15,7]
]
*/

import (
	"container/list"
)

func levelOrder(root *TreeNode) [][]int {
	var res [][]int // 设置res用来保存输出结果

	if root == nil {
		return res
	} // 边界情况处理

	queue := list.New() // 设置一个队列，用来存储二叉树中的元素
	queue.PushBack(root)
	isOddNumber := false // 用来判断当前的层数是否为奇数层，初始化在第0层，为偶数层

	for queue.Len() > 0 { // 遍历队列，直到队列为空，说明访问了二叉树中所有的节点
		size := queue.Len()        // 用来记录queue的长度，即每层节点的个数
		isOddNumber = !isOddNumber // 奇偶层总是交替出现的  通过取反操作，判断当前的层数是否为奇偶层  由于isOddNumber初始化为false，所以第一次进来这个for循环取反后为true，符合第一层是奇数层的定义

		var temp []int // 生成一个切片temp，用来保存每一层节点，保存成功后添加到res中

		for i := 0; i < size; i++ { // 使用for循环，将queue中的元素按照给定的规则添加到temp中

			node := queue.Remove(queue.Front()).(*TreeNode) // 从queue中取出一个节点
			if isOddNumber {                                // 如果是奇数层，那么按照顺序添加到切片temp的尾部
				temp = append(temp, node.Val)
			} else {
				temp = append([]int{node.Val}, temp...) // 如果是偶数层，那么按顺序添加到切片temp的头部
			}

			if node.Left != nil { // 判断当前节点的左右子节点是否有值，如果有，则添加到queue中
				queue.PushBack(node.Left)
			}
			if node.Right != nil {
				queue.PushBack(node.Right)
			}
		}

		res = append(res, temp) // 把存放了每一层元素的切片temp添加到res中
	}

	return res // 返回res
}
